package com.nanbei.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @ClassDescription: Floyd-Warshall 算法是一种经典的多源最短路径算法，用于计算给定加权图中所有顶点之间的最短路径。
 * 与 Dijkstra 和 Bellman-Ford 不同，Floyd-Warshall 可以处理带有负权边的图，但要求图中没有负权环。
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/2 14:45
 */
public class FloydWarshall {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.setEdges(Arrays.asList(new Edge(v3, -2)));
        v2.setEdges(Arrays.asList(new Edge(v1, 4), new Edge(v3, 3)));
        v3.setEdges(Arrays.asList(new Edge(v4, 2)));
        v4.setEdges(Arrays.asList(new Edge(v2, -1)));
        List<Vertex> graph = Arrays.asList(v1, v2, v3, v4);


        /*
                直接连通
                v1  v2  v3  v4
            v1  0   ∞   -2  ∞
            v2  4   0   3   ∞
            v3  ∞   ∞   0   2
            v4  ∞   -1  ∞   0

                k=0 借助v1到达其它顶点
                v1  v2  v3  v4
            v1  0   ∞   -2  ∞
            v2  4   0   2   ∞
            v3  ∞   ∞   0   2
            v4  ∞   -1  ∞   0

                k=1 借助v2到达其它顶点
                v1  v2  v3  v4
            v1  0   ∞   -2  ∞
            v2  4   0   2   ∞
            v3  ∞   ∞   0   2
            v4  3   -1  1   0

                k=2 借助v3到达其它顶点
                v1  v2  v3  v4
            v1  0   ∞   -2  0
            v2  4   0   2   4
            v3  ∞   ∞   0   2
            v4  3   -1  1   0

                k=3 借助v4到达其它顶点
                v1  v2  v3  v4
            v1  0   -1   -2  0
            v2  4   0   2   4
            v3  5   1   0   2
            v4  3   -1  1   0
         */

        floydWarshall(graph);
    }

    private static void floydWarshall(List<Vertex> graph) {
        int size = graph.size();
        int[][] ints = new int[size][size];
        // 用来记录当前节点的前一个节点
        Vertex[][] prev = new Vertex[size][size];

        //初始化 距离矩阵和 前驱矩阵
        for (int i = 0; i < graph.size(); i++) {
            // 获取当前节点
            Vertex vertex = graph.get(i);
            // 获取当前节点的关联节点
            List<Edge> edges = vertex.getEdges();
            Map<Vertex, Integer> vertexIntegerMap = edges.stream().collect(Collectors.toMap(Edge::getLinked, Edge::getWeight));
            for (int j = 0; j < graph.size(); j++) {
                Vertex ver = graph.get(j);
                if (vertex == ver) {
                    // 如果当前节点和该节点相等则为同一节点，距离为0
                    ints[i][j] = 0;
                } else {
                    // 如果当前节点的关联节点包含该节点则添加到数组中
                    ints[i][j] = vertexIntegerMap.getOrDefault(ver, Integer.MAX_VALUE);
                    if (vertexIntegerMap.containsKey(ver)){
                        prev[i][j] = vertex;
                    }
                }
            }
        }

        /**
         * 外层 for 循环 (k):
         * 表示当前考虑的中间顶点。这个顶点用于尝试更新所有其他顶点对之间的路径。如果路径通过这个顶点可以更短，就更新路径。
         * 该循环依次将每个顶点作为中间顶点。
         *
         * 中间 for 循环 (i):
         * 表示起始顶点。这个循环遍历图中的每一个顶点，作为路径的起点。
         * 通过每个顶点对，尝试找到从起始顶点到其他所有顶点的最短路径。
         *
         * 内层 for 循环 (j):
         * 表示终点。这个循环遍历图中的每一个顶点，作为路径的终点。
         * 尝试通过当前的中间顶点更新从起始顶点到终点的最短路径。
         */
        for (int k = 0; k < graph.size(); k++) {
            for (int i = 0; i < graph.size(); i++) {
                for (int j = 0; j < graph.size(); j++) {
                    if (ints[i][k] != Integer.MAX_VALUE &&
                            ints[k][j] != Integer.MAX_VALUE &&
                            ints[i][k] + ints[k][j] < ints[i][j]) {
                        ints[i][j] = ints[i][k] + ints[k][j];
                        prev[i][j] = prev[k][j];
                    }

                }
            }
        }

        print(prev);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                path(prev,graph,i,j);
            }
        }


    }

    static void print(int[][] dist) {
        System.out.println("-------------");
        for (int[] row : dist) {
            System.out.println(Arrays.stream(row).boxed()
                    .map(x -> x == Integer.MAX_VALUE ? "∞" : String.valueOf(x))
                    .map(s -> String.format("%2s", s))
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }

    static void path(Vertex[][] prev, List<Vertex> graph, int i, int j) {
        LinkedList<String> stack = new LinkedList<>();
        System.out.print("[" + graph.get(i).getName() + "," + graph.get(j).getName() + "] ");
        stack.push(graph.get(j).getName());
        while (i != j) {
            Vertex p = prev[i][j];
            stack.push(p.getName());
            j = graph.indexOf(p);
        }
        System.out.println(stack);
    }

    static void print(Vertex[][] prev) {
        System.out.println("-------------------------");
        for (Vertex[] row : prev) {
            System.out.println(Arrays.stream(row).map(v -> v == null ? "null" : v.getName())
                    .map(s -> String.format("%5s", s))
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }
}
